package LeetCode;

import com.sun.org.apache.regexp.internal.RE;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:57
 */
public class LeetCode215 {
    /**
     * 215. 数组中的第K个最大元素
     * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     */

    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        System.out.println();
        System.out.println(indexTest(nums, 3));
        System.out.println(new LeetCode215().quick_sort(nums, 0,nums.length-1,3));
    }

    public static int indexTest(int[] nums,int k){
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });
        for (int num : nums) {
            queue.add(num);
        }
        for (int i = 0; i < k - 1; i++){
            queue.poll();
        }
        return queue.poll();
    }

    //使用快排思想
    public int quick_sort(int[] nums,int left,int right,int k) {
        int i = left;
        int j = left;
        int pivot = nums[right];//最右边的数
        int len = right - left + 1;

        if (left < right) {
            //从大到小对数组进行快排
            for (; j < right; j++) {
                if (nums[j] > pivot) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    i++;
                }
            }

            nums[j] = nums[i];
            nums[i] = pivot;

            // pivot 此时位于索引 i 处，i - left + 1 表示 pivot 是第几大的数
            int which_max = i - left + 1;
            if (which_max == k) // pivot 正好是第 k 大的数
            {
                return pivot;
            }

            // 第 k 大的数在 pivot 右边，问题转化为找右边数组第 (k - which_max) 大的元素
            // 比如 pivot 是第四大的数，要找第五大的数，则继续找右边数组第一大的数即可
            else if (which_max < k) {
                return quick_sort(nums, i + 1, right, k - which_max);
            }

            // 第 k 大的数在 pivot 左边，问题转化为找左边数组第 k 大的元素
            // 比如 pivot 是第三大的数，要找第二大的数，则继续找左边数组第二大的数即可
            else {
                return quick_sort(nums, left, i - 1, k);
            }

        } else {
            return pivot;
        }
    }



    //先用时间复杂度
    public int findKthLargest(int[] nums, int k) {
        if (nums.length == 0 || nums == null){
            return -1;
        }
        heap_sort(nums,nums.length);
        return nums[k - 1];
    }




    /**
     * 最小堆顶化 自己写个堆排序或者使用现成的队列函数
     * @param nums
     * @param n 数组长度
     * @param i 起始下标
     */
    public void heapify(int[] nums,int n,int i){
        int max = i;
        int left = 2 * i + 1;// 左子树
        int right = 2 * i + 2;// 右子树
        //开始进行小顶堆的判断
        if (left < n && nums[left] < nums[max]){
            max = left;
        }
        if (right < n && nums[right] < nums[max]){
            max = right;
        }
        if (i != max){
            int temp = nums[i];
            nums[i] = nums[max];
            nums[max] = temp;
            heapify(nums,n,max);
        }
    }

    public void bulid_heap(int[] nums,int n){
        int last_node = n - 1;
        int last_node_parent = (last_node - 1) / 2;//根据公式进行的推导
        for (int i = last_node_parent; i >= 0; i--){
            heapify(nums,n,i);
        }
    }

    public void heap_sort(int[] nums,int n){//进行堆排序
        //先进行一次堆顶化
        bulid_heap(nums,n);
        for (int i = n - 1; i >= 0; i--){
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            heapify(nums,i,0);//破坏了大顶堆，进行一次堆顶化
        }
    }

}
